<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    382. Linked List Random Node
   </h1>
   <p>
    Given a singly linked list, return a random node's value from the linked list. Each node must have the
    <b>
     same probability
    </b>
    of being chosen.
   </p>
   <p>
    <b>
     Follow up:
    </b>
    <br>
    What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
   </p>
   <p>
    <b>
     Example:
    </b>
   </p>
   <pre>
// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
</pre>
  </div>
  <div>
   <h1 class="question_title">
    382. 链表随机节点
   </h1>
   <p>
    给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点
    <strong>
     被选的概率一样
    </strong>
    。
   </p>
   <p>
    <strong>
     进阶:
    </strong>
    <br>
    如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
   </p>
   <p>
    <strong>
     示例:
    </strong>
   </p>
   <pre>
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();
</pre>
  </div>
 </body>
</html>